package madixin.t677;

class MapSum {

    private Node root = new Node();

    /**
     * Initialize your data structure here.
     */
    public MapSum() {

    }

    public void insert(String key, int val) {
        insert(key, val, root);
    }

    private void insert(String key, int val, Node node) {
        if (key == null || key.equals("")) {
            node.value = val;
            return;
        }
        if (node.child[key.charAt(0) - 'a'] == null) {
            Node newNode = new Node();
            node.child[key.charAt(0) - 'a'] = newNode;
        }
        insert(key.substring(1), val, node.child[key.charAt(0) - 'a']);
    }

    public int sum(String prefix) {
        Node node = searchNode(prefix, root);
        return getNodeSum(node);
    }

    private int getNodeSum(Node node) {
        if (node == null) {
            return 0;
        }
        int sum = node.value;
        for (int i = 0; i < node.child.length; i++) {
            if (node.child[i] != null) {
                sum += getNodeSum(node.child[i]);
            }
        }
        return sum;
    }

    private Node searchNode(String prefix, Node node) {
        if (prefix == null || prefix.equals("")) {
            return node;
        }
        if (node.child[prefix.charAt(0) - 'a'] == null) {
            return null;
        }
        return searchNode(prefix.substring(1), node.child[prefix.charAt(0) - 'a']);
    }


    class Node {
        private Node[] child = new Node[26];
        private int value;
    }

}